package com.heima.leetcode.practice;

import java.util.Arrays;
import java.util.HashMap;

/**
 * leetcode 1 两数之和
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/15 21:35
 */
public class E1 {

    /**
     * <h3>方法一：用hash表</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引数组
     */
    public int[] twoSum1(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index == null) {
                map.put(target - nums[i], i);
            } else {
                result[0] = index;
                result[1] = i;
                break;
            }
        }
        return result;
    }

    /**
     * <h3>方法二：双指针，但是这种方式不好返回原始的索引，但是可以返回对应组合的值</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引数组
     */
    public int[] twoSum2(int[] nums, int target) {
        Arrays.sort(nums);
        int[] result = new int[2];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                result[0] = nums[left];
                result[1] = nums[right];
                break;
            }
        }
        return result;
    }
}
